package 力扣.二分;

import java.util.Random;

public class QS2 {
    static Random random = new Random();
    public static void main(String[] args) {
        int arr[] = {2,3,4,5,6,100,99};
//        int[] arr=new int[]{0,1,2,4,5,1,12,2,444,1321,12,1234134,143241,-1,7,7,7,7,7,-1,-100,3,3,3};
//        int[] arr=new int[]{3,1,2};
        int k = 1;
        int index = arr.length - k;
        int re=findKthLargest(arr, 0, arr.length-1,index);
        System.out.println(re);

    }
    private  static int  findKthLargest(int[] arr, int start,int end,int index) {
        int p =randomPartition(arr, start, end);//得到轴值（确定一个数的位置）
        if (index == p){//判断轴值是否是要找的那个数
            return arr[p];//若是则直接返回
        }else {//若不是则判断大小，进入下一层递归重新得到新的轴值
            return  p > index ? findKthLargest(arr, start, p-1,index) : findKthLargest(arr, p+1, end,index);
        }
    }

    /**
     * 快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n - 1，每次递归的时候又向 n - 1的集合中递归。
     * 这种情况是最坏的，时间代价是 O(n ^ 2)
     * 我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)。
     * @return
     */
    public static int randomPartition(int[] arr, int l, int r) {
        int i = random.nextInt(r - l + 1) + l;//从 r 到 l 之间选取一个随机数作为基准点
        swap(arr, i, r);
        return qsort2(arr, l, r);//进入qsort方法
    }

    /**
     * 原理：根据快排原理，将数组（start ~ end）中小于轴值的元素交换至其左边，大于轴值的元素交换至其右边。
     *      这样就确定了轴值的位置。
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private static int  qsort2(int arr[],int start,int end) {
        int p = start - 1;//p 暂时赋值为start - 1 ,以后p从start开始递增
        int te = arr[end];//te 暂存基准点元素
        for (int i = start; i < end; i++) {//从左边开始遍历
            //若小于te(基准元素) 则将其和p交换
             if (arr[i] < te){
                 swap(arr, ++p, i);//交换 ，p向右递增（ 也就是让数组中p左边的元素都小于轴值（即基准点） ）
             }
        }
        swap(arr, ++p, end);//将 轴值（基准点）交换至中间，使轴值左边的都小于轴值 ，右边的都大于轴值。也就确定了轴值的位置
        return p;//得到轴值
    }


    private  static void swap(int []arr,int i,int j) {//交换函数
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
